package Midium;

// 63.不同路径II
/*
 * dp[i][j] = dp[i-1][j]+dp[i][j-1]
 * 如果给的obstacleGrid里对应的位置为1，则dp[i][j] = 0
 * */
public class Solution63 {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int dp[][] = new int[m][n]; // 初始默认全为0
        dp[0][0] = 1;
        int x, y;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (obstacleGrid[i][j] == 1) {
                    // 虽然默认全为0，但是要考虑到只有一行一列 且为障碍物的情况
                    dp[i][j] = 0;
                    continue;
                }
                if (i == 0 && j == 0) continue;
                try {
                    x = dp[i - 1][j];
                } catch (Exception e) {
                    x = 0;
                }
                try {
                    y = dp[i][j - 1];
                } catch (Exception e) {
                    y = 0;
                }
                dp[i][j] = x + y;
            }
        }
        return dp[m - 1][n - 1];
    }
}
